'''
给定两个正整数变量：

height: 楼梯的台阶数 (height >= 0)
max_steps: 一次可以迈的最大的台阶数 (max_steps >= 1)

编写一个函数 staircase，计算一次最多迈 max_steps 的情况下，走到 height 台阶数的方法。

例如：

height: 3
max_steps: 2

表示有 3 个台阶，一次最多可以迈 2 个台阶。这样的话，我们有 3 种方法走到台阶顶部：

* 一种是一次走一步；
* 一种是一次走两步，再走一次；
* 一种是一次走一步，再走两步；

因此，staircase(3, 2) 应该返回 3。
'''

def staircase(height, max_steps):
    if height == 0 or height == 1:
        return 1

    steps = 0
    for i in range(1, min(height, max_steps) + 1):
        steps += staircase(height - i, max_steps)

    return steps

print(staircase(3, 2))

def staircase_with_cache(height, max_steps, cache):
    if height in cache:
        return cache[height]
    
    if height == 0 or height == 1:
        return 1

    steps = 0
    for i in range(1, min(height, max_steps) + 1):
        steps += staircase(height - i, max_steps, cache)
        
    cache[height - i] = steps

    return steps

def staircase_iterative(height, max_steps):
    steps = [0] * (height + 1)
    steps[0] = 1
    steps[1] = 1

    for currHeight in range(2, height + 1):
        i = 1 # steps we moved back from current height

        while i <= currHeight and i <= max_steps:
            steps[currHeight] += steps[currHeight - i]
            i += 1
    
    return steps[height]

print(staircase_iterative(5, 4))